﻿using System;
using OptimalisationFramework.Interfaces;
using System.Collections;

namespace OptimalisationFramework
{
    namespace Problems
    {
        struct Point
        {
            private int x, y;

            public int Y
            {
                get { return y; }
                set { y = value; }
            }

            public int X
            {
                get { return x; }
                set { x = value; }
            }
            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
            public static bool operator ==(Point p1, Point p2)
            {
                return (p1.x == p2.x && p1.y == p2.y);
            }

            public static bool operator !=(Point p1, Point p2)
            {
                return !(p1 == p2);
            }

            public override bool Equals(object o)
            {
                return this == (Point)o;
            }

            public override int GetHashCode()
            {
                return 0;
            }

        };

        struct Edge
        {
            private Point b, e;

            internal Point B
            {
                get { return b; }
            }

            internal Point E
            {
                get { return e; }
            }

            public Edge(Point begin, Point end)
            {
                b = begin;
                e = end;
            }

            public static bool operator ==(Edge e1, Edge e2)
            {
                return ((e1.b == e2.b && e1.e == e2.e) || (e1.b == e2.e && e1.e == e2.b));
            }

            public static bool operator !=(Edge e1, Edge e2)
            {
                return !(e1 == e2);
            }

            public override bool Equals(object o)
            {
                return this == (Edge)o;
            }

            public override int GetHashCode()
            {
                return 0;
            }
            public string toString()
            {
                return "(" + b.X + ", " + b.Y + ") - (" + e.X + ", " + e.Y + ")";
            }
        };

        class ShortestPathProblem : ITrajectorySearch
        {
            /*
             * Attributes
             * */
            public bool[,] labyrinth;
            private int size;
            private double percentageWalls;
            private double adjustRate;
            private Random r;
            private Point end;
            private Hashtable afstanden;
            private ArrayList edges;
            private object locker;


            /*
             * Constructor
             * */
            public ShortestPathProblem(int size, double percentageWalls, double adjustRate, Point end)
            {
                if (percentageWalls < 0 || percentageWalls > 1)
                {
                    throw (new Exception("Wrong wall percentage"));
                }
                if (adjustRate < 0 || adjustRate > 1)
                {
                    throw (new Exception("Wrong adjust percentage"));
                }


                this.end = end;
                this.adjustRate = adjustRate;
                this.size = size;
                locker = new object();
                this.percentageWalls = percentageWalls;
                // intialize labyrinth
                // true is walkable, false is not walkable
                labyrinth = new bool[size, size];
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        labyrinth[i, j] = true;
                    }
                }

                // random function
                r = new Random();
            }

            public int Size
            {
                get { return size; }
            }


            public ITrajectorySearch GenerateInitialSolution()
            {
                lock (locker)
                {
                    // set walls
                    int numberOfWalls = (int)Math.Ceiling(Math.Pow(size, 2) * percentageWalls);
                    for (int i = 0; i < numberOfWalls; i++)
                    {
                        int x = r.Next(0, size), y = r.Next(0, size);
                        while (!labyrinth[x, y])
                        {
                            x = r.Next(0, size);
                            y = r.Next(0, size);
                        }
                        labyrinth[x, y] = false;
                    }                    

                    //labyrinth = new bool[,]{ {true,true,true,true,true},{false,false,false,false,true},{true,true,true,true,true},{true,false,false,false,false},{true,true,true,true,true} };
                    int numberOfWalkablePoints = (int)Math.Ceiling((Math.Pow(size, 2) * percentageWalls));
                    afstanden = new Hashtable(numberOfWalkablePoints);
                    // init 1
                    for (int i = 0; i < size; i++)
                    {
                        for (int j = 0; j < size; j++)
                        {
                            afstanden.Add(i + "-" + j, (i == 0 && j == 0) ? 0 : int.MaxValue - 1); // 2147483646                    
                        }
                    }
                    edges = BuildEdges();
                }
                return this;
            }

            public bool StopSearch()
            {
                // size*2-2 is the best possible solution
                // *1 percentage that shows how similar the current solution should be with the best solution
                if (ObjectifFunction() <= (size * 2 - 2) * 120)
                {
                    return true;
                }
                return false;
            }

            public ITrajectorySearch AdjustSolution()
            {                
                int adjustPlaces = (int)((size * size) * adjustRate);
                ArrayList alreadyChanged = new ArrayList(adjustPlaces);
                int i = 0;
                while (i < adjustPlaces)
                {
                    int x = r.Next(0, size), y = r.Next(0, size);
                    if (!alreadyChanged.Contains(x + "-" + y))
                    {
                        labyrinth[x, y] = !labyrinth[x, y];
                        alreadyChanged.Add(x + "-" + y);
                        i++;
                    }
                }
                return this;
            }

            public double ObjectifFunction()
            {
                return (double)BellmanFord();
            }

            public double distance()
            {
                return (double)(((int)afstanden[end.X + "-" + end.Y]));
            }

            private int BellmanFord()
            {
                lock (locker)
                {
                    // afstanden instellen voor begin naar alle punten
                    for (int i = 0; i < size * size - 1; i++)
                    {
                        foreach (Edge v in edges)
                        {                            
                            Point b = v.B, e = v.E;
                            if ((int)afstanden[e.X + "-" + e.Y] > (int)afstanden[b.X + "-" + b.Y] + 1)
                            {
                                int afstand = (int)afstanden[e.X + "-" + e.Y];
                                afstanden.Remove(e.X + "-" + e.Y);
                                afstand = ((int)afstanden[b.X + "-" + b.Y] == -1 ? 0 : (int)afstanden[b.X + "-" + b.Y]) + 1;
                                afstanden.Add(e.X + "-" + e.Y, afstand);
                            }
                        }
                    }
                }
                return ((int)afstanden[end.X + "-" + end.Y]);
            }

            private ArrayList BuildEdges()
            {
                ArrayList edges = new ArrayList();
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        if (isWalkable(i, j))
                        {
                            // X - 1
                            if (isWalkable(i - 1, j) && !edges.Contains(new Edge(new Point(i, j), new Point(i - 1, j))))
                            {
                                edges.Add(new Edge(new Point(i, j), new Point(i - 1, j)));
                            }
                            // Y - 1
                            if (isWalkable(i, j - 1) && !edges.Contains(new Edge(new Point(i, j), new Point(i, j - 1))))
                            {
                                edges.Add(new Edge(new Point(i, j), new Point(i, j - 1)));
                            }
                            // X + 1
                            if (isWalkable(i + 1, j) && !edges.Contains(new Edge(new Point(i, j), new Point(i + 1, j))))
                            {
                                edges.Add(new Edge(new Point(i, j), new Point(i + 1, j)));
                            }
                            // Y + 1
                            if (isWalkable(i, j + 1) && !edges.Contains(new Edge(new Point(i, j), new Point(i, j + 1))))
                            {
                                edges.Add(new Edge(new Point(i, j), new Point(i, j + 1)));
                            }
                        }
                    }
                }
                return edges;
            }

            private bool isWalkable(int x, int y)
            {
                if (x < 0 || x >= size || y < 0 || y >= size)
                {
                    return false;
                }
                return labyrinth[x, y];
            }


            public void WriteLabyrinth()
            {
                Console.WriteLine();
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        Console.Write(labyrinth[i, j] ? "[]" : "**");
                    }
                    Console.WriteLine();
                }
            }

        }
    }
}
